'''
树与二叉树
    根节点,叶子结点
    树的深度(高度)
    树的度(拥有最多分差的结点的分叉数)
    子节点/父节点
    子树

    二叉树:度不超多2的树,两个子节点叫左子节点,右子节点
    满二叉树:每一个层的节点数都达到最大值
    完全二叉树:叶结点只能出现在最下层和次下层,
    并且最下面一层的结点都集中在该层最左边的若干位置的二叉树
    二叉树的存储方式:
        链式存储方式
        顺序存储方式
        父节点和子节点下标数字的关系:
            父节点i 子节点 = 2i+1,2i+2
            子节点i 父节点 = (i-1)//2
'''

'''
堆排序 
    堆:一种特殊的完全二叉树
    大根堆:一课完全二叉树,满足任意节点都比其子节点大
    小根堆:一课完全二叉树,满足任一节点都比其子节点小
    
堆的向下调整:
    假设:结点的左右子树都死堆,但自身不是堆
        当根节点的左右子树都是堆时,可以通过一次向下的调整来将其变换成一个堆
'''
'''
堆排序过程:
    1.建立堆
    2.得到堆顶元素,为最大元素
    3.去掉堆顶,将堆最后一个元素放到堆顶,此时可通过一次调整重新使堆有序
    4.堆顶元素为第二大元素
    5.重复步骤3,直到堆变空
'''
def sift(li,low,high):
# li:列表 ,low:堆的堆顶元素 ,high:堆的最后一个元素
    i = low  # i指向根节点
    j = 2*i + 1  # j是i的左孩子
    tmp = li[low]   # 把堆顶存起来
    while j<= high:   # 只要j位置有数据
        if j + 1 <= high and li[j+1] > li[j]:  #如果右孩子首先要有并且比较大
            j = j + 1   # 把j 指向右孩子
        if li[j] > tmp:
            li[i] = li[j]
            i = j
            j = 2 * i + 1
        else:   #tmp更大,把tmp放到i的位置上
            li[i] = tmp
            break
    else:
        li[i] = tmp  # 把tmp最后的叶子结点上

def heap_sort(li):
    n = len(li)
    for i in range((n-2)//2 -1,-1,-1):
        # i表示键堆的时候调整的部分的根结点的下标
        sift(li,i,n-1)
    # 建堆完成了
    for i in range(n-1,-1,-1):
        # i指向当前堆的最后一个元素
        li[0],li[i] = li[i],li[0]
        sift(li,0,i-1)  # i-1是新的high,即最后一个元素位置

li = [i for i in range(100)]
import random
random.shuffle(li)
print(li)

heap_sort(li)
print(li)